COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00011 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.cb NOTES ON QUEEN AND KING vs. ROOK AND KING

	#. A straight tree search apparently won't work, because
the tree is too large, but there are
only 64↑4 positions and an approximate eightfold symmetry, so
it is reasonable to make a table indexed by positions and store
in each position the number of moves to mate.  It
may be simpler, if not quite as elegant, to store the number
of moves to capturing the rook.

	Such a table would have about two million entries each of
six bits.  This would require using extended storage on the PDP-10,
so let's see if we can't do with less.

	#. Some of the two million positions are illegal, in some
the rook will be immediately captured or the white queen.  In
others white can force the capture of the rook by a small number
of checks.  Therefore, we can consider storing the positions along
with the number of moves to win.  If we had to store the positions
of each piece, this would be 24 bits plus 6 bits for the number of
move which we might as well round up to a 36 bit word.  We
would win on storage provided the size of the table was reduced
by a factor of six.

	#. By going to a mixed system, we can reduce storage
requirements much more.  Namely, we may use the positions of
the first three pieces as an index into a table that
stores the locations of subtables in which are listed the positions
of the fourth piece and the number of moves.  This reduces the
size of the entry to 12 bits.  The auxiliary table would have
an approximately 15 bit index, and the entry would be a pointer
of not more than 18 bits, so we would need about 16,000 words
for it.  The entries in the main table can be reduced further in
size if we sort them by number of moves to win and store only
the position of the last piece.  This brings us back to six
bits per entry with a little overhead, but now we are storing
information only about significant positions.

	Actually there will be some overhead, and to reduce it
we may need to take an extra bit from the index and put it in
the table entry in order to have more entries per number of moves
to win.

	#. The next compaction is to store positions only when
the number of moves to win is even (or divisible by 4 or 6).
Using the table from an arbitrary position then requires lookahead
to find either an immediate win or a position whose number of
moves to win is stored.  This trades compute time in the use of
the table for table size.  The trade-off depends on the efficiency
of look-ahead.

	#. It seems plausible that with these devices we can reduce
the size of the main table to less than 128K words.  This will
permit the program and all its data to fit into a single 256K
core image so that neither extended addressing nor disk use will
be required.

	#. The look-ahead should use alpha-beta, position storage
to detect transpositions, and a good move orderer possibly using
the killer heuristic.  A superficial examination suggests that
black will ordinarily have about 5 moves that don't lose his rook
to an attack containing only checks and pins and that white has
about 10 plausible moves.  This suggests that the program that
uses the tables may be able to look ahead six plies or maybe even
eight if a good move orderer can be found.

	#. It would be interesting if the size of the tables could
be reduced to the point where they could fit in the memory of the
Alto or if we could imagine Fidelity Electronics offering a
queen vs. rook player with the tables stored in ROM.  The ideas
advanced so far don't seem to be quite good enough for either
of these goals, although good fortune with the look-ahead might
make it.

	#. The following algorithm will work.  Make a table of
bits, one for each of the 2 million positions all set initially
to zero.  Initialize by scanning all two million and setting to
1 the bits corresponding to
positions in which white has won.  With some extra fuss this can
be taken as checkmate or we can settle for capturing the rook
without stalemate.  Each subsequent step consists of scanning the
table and for each position not already marked doing a two ply
lookahead to see if white can force a position in the table.
If we have two tables, we can do one ply lookaheads.  Whenever,
we find a position that is won, we mark it.  At certain stages,
according to the desired compromise between lookahead and table
size in the game playing program, we write each position as it
is found together with the stage number into the a table of
significant positions of the form described above.

	#. The main table is two or four million bits according
too the desired compromise between run time and memory use in
the table building program.  Actually more bits can speed up
the program.  A table of illegal positions can help in two ways;
first the scan can pass these positions easily and second the
legal move routines might use them to check for moving into check
or stalemate or occupying the same square as one's own piece.
Aha!  If we use 4 million bits, the illegal positions can be
incorporated in the table of won positions in the W to move table,
since an illegal move for black can be regarded as a move to a
position that white has won.  This means that when we consider
a W move we can skip the illegal positions just as we skip positions
in which W has already won.